package com.lonely;

import lombok.Data;

import java.util.*;

/**
 * @author 黄志标
 * @date 2023/4/14 13:42
 * @Description: https://leetcode.cn/problems/binary-tree-inorder-traversal/
 * <p>
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 * 你可以按任意顺序返回答案。
 */
public class Question94_中序遍历 {


    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);

        treeNode1.left = null;
        treeNode1.right = treeNode2;

        treeNode2.left = treeNode3;
        treeNode2.right = null;

        List<Integer> integers =inorderTraversal(treeNode1);
        System.out.println(integers);

    }


    /**
     * 思路：
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        while (temp != null || !stack.isEmpty()) {
            if (temp != null) {
                stack.push(temp);
                temp = temp.left;
            } else {
                TreeNode pop = stack.pop();
                result.add(pop.val);
                temp = pop.right;
            }
        }
        return result;
    }


    @Data
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
